#define _CRT_SECURE_NO_WARNINGS

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
        return true;
    if ((p && q == NULL) || (p == NULL && q))
    {
        return false;
    }
    if (p->val == q->val)
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    else
        return false;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL)
        return false;
    if (root->val == subRoot->val && isSameTree(root, subRoot))
        return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}


//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    if ((p && q == NULL) || (p == NULL && q))
//    {
//        return false;
//    }
//    if (p->val == q->val)
//        return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
//    else
//        return false;
//}
//bool isSymmetric(struct TreeNode* root) {
//    return isSameTree(root->left, root->right);
//}

//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    if ((p && q == NULL) || (p == NULL && q))
//    {
//        return false;
//    }
//    if (p->val == q->val)
//        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//    else
//        return false;
//}


//void preOrder(struct TreeNode* root, int* size)
//{
//    if (root == NULL)
//        return;
//    if (root)
//        (*size)++;
//    preOrder(root->left, size);
//    preOrder(root->right, size);
//}
//void CreateTree(struct TreeNode* root, int* ret, int* i)
//{
//    if (root == NULL)
//        return;
//    if (root)
//    {
//        ret[(*i)++] = root->val;
//    }
//    CreateTree(root->left, ret, i);
//    CreateTree(root->right, ret, i);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = 0;
//    preOrder(root, returnSize);
//    int* ret = (int*)malloc(sizeof(int) * (*returnSize));
//    int i = 0;
//    CreateTree(root, ret, &i);
//    return ret;
//}


//#include <stdio.h>
//#include <stdlib.h>
//typedef struct BinaryTreeNode
//{
//    char val;
//    struct BinaryTreeNode* left;
//    struct BinaryTreeNode* right;
//}BTNode;
//
//BTNode* CreateTree(char* arr, int* i)
//{
//    if (arr[*i] == '#')
//    {
//        (*i)++;
//        return NULL;
//    }
//    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
//    root->left = NULL;
//    root->right = NULL;
//    root->val = arr[(*i)++];
//    root->left = CreateTree(arr, i);
//    root->right = CreateTree(arr, i);
//    return root;
//}
//
//void inOrder(BTNode* root)
//{
//    if (root == NULL)
//        return;
//    inOrder(root->left);
//    printf("%c ", root->val);
//    inOrder(root->right);
//}
//int main() {
//    char arr[100] = { 0 };
//    scanf("%s", arr);
//    int i = 0;
//    BTNode* root = NULL;
//    root = CreateTree(arr, &i);
//    inOrder(root);
//    return 0;
//}